import random

N = 32  # num of queens


def get_conflicts_num(status):
    num = 0
    for i in range(len(status)):
        for j in range(i + 1, len(status)):
            if status[i] == status[j]:
                num += 1
            if abs(status[i] - status[j]) == (j - i):
                num += 1
    return num


def hill_climbing(status):
    dic = {}  # dictionary
    flag = 0
    length = len(status)
    for i in range(length):
        for j in range(length):
            if status[i] == j:
                continue
            new_status = list(status)
            new_status[i] = j
            # 首选爬山法
            #     if get_conflicts_num(new_status) < get_conflicts_num(status):
            #         flag = 1
            #         status[i] = j
            #         break
            # if flag:
            #     break
            # endof 首选爬山法
            # 随机爬山法/随机重启爬山法
            dic[(i, j)] = get_conflicts_num(new_status)
    ans = []  # list
    conflicts = get_conflicts_num(status)

    for k, v in dic.items():
        if v < conflicts:
            conflicts = v
    for k, v in dic.items():
        if v == conflicts:
            ans.append(k)
    if len(ans) > 0:
        rdnum = random.randint(0, len(ans) - 1)
        i = ans[rdnum][0]  # 随机爬山法第一坐标用rdnum，首选和随机重启用0
        j = ans[rdnum][1]
        status[i] = j
    # endof 随机爬山法/随机重启爬山法
    return status


def init_status():
    status = []
    for i in range(N):  # 0~N-1
        status.append(random.randint(0, N-1))
    return status


def solve():
    status = init_status()  # initial status
    # 随机重启爬山法
    # p_status = list(status)
    # pp_status = list(p_status)
    # endof 随机重启爬山法
    print("initial status:", status)
    while get_conflicts_num(status) > 0:
        status = hill_climbing(status)
        # 随机重启爬山法
        # if pp_status == status:
        #     status = init_status()
        # pp_status = list(p_status)
        # p_status = list(status)
        # endof 随机重启爬山法
        print("status:", status)
        print("conflicts:", get_conflicts_num(status))
    print("final ans:")
    print(status)


if __name__ == '__main__':
    solve()
